//
// Created by LiuYou on 2021/5/10.
//

#include <array>
#include <vector>
#include <iostream>


static std::vector<int> quickSort(std::vector<int>& array);

int main() {

    std::array<int, 5> arr{54, 22, 65, 11, 661};
    std::vector<int> vec{arr.cbegin(), arr.cend()};

    const std::vector<int>& vectorResult = quickSort(vec);

    for (const auto& item : vec) {
        std::cout << item << " ";
        std::fflush(stdout);
    }
    std::cout << std::endl;
    for (const auto& result : vectorResult) {
        std::cout << result << " ";
        std::fflush(stdout);
    }

    return 0;
}

static std::vector<int> quickSort(std::vector<int>& array) {
    // 基线条件
    if (array.size() < 2) {
        return array;
    } else {
        // 递归条件
        int pivot = array[0];

        std::vector<int> less{};
        for (int i = 1; i < array.size(); ++i) {
            if (array[i] <= pivot) {
                less.push_back(array[i]);
            }
        }
        std::vector<int> greater{};
        for (int i = 1; i < array.size(); ++i) {
            if (array[i] > pivot) {
                greater.push_back(array[i]);
            }
        }

        std::vector<int> vector = quickSort(less);
        vector.insert(vector.cend(), pivot);
        const std::vector<int>& greaterTmp = quickSort(greater);
        vector.insert(vector.cend(), greaterTmp.cbegin(), greaterTmp.cend());
        return vector;
    }
}


#ifdef TEST01
/**
 * 写出了快排, 可以运行成功。
 */
namespace Test01 {
    //static std::array<int, 5>& quickSort(std::array<int, 5>& array);
    static std::vector<int> quickSort(std::vector<int>& array);

    int main() {

        std::array<int, 5> arr{54, 22, 65, 11, 661};
        std::vector<int> vec{arr.cbegin(), arr.cend()};

        const std::vector<int>& vectorResult = quickSort(vec);

        for (const auto& item : vec) {
            std::cout << item << " ";
            std::fflush(stdout);
        }
        std::cout << std::endl;
        for (const auto& result : vectorResult) {
            std::cout << result << " ";
            std::fflush(stdout);
        }

        return 0;
    }

//static std::array<int, 5>& quickSort(std::array<int, 5>& array) {
    static std::vector<int> quickSort(std::vector<int>& array) {
        // 基线条件
        if (array.size() < 2) {
            return array;
        } else {
            // 递归条件
            int pivot = array[0];
/*        for (int i = 1; i < array.size(); ++i) {
            if (array[i] > pivot) {
                continue;
            } else if (array[i] == pivot) {
                continue;
            } else {
                int tmp = pivot;
                pivot = array[i];
                pivot = tmp;
            }
        }*/

/*        std::array<int, 5> less{};
        for (int i = 1; i < array.size(); ++i) {
            if (array[i] <= pivot) {
                less[i - 1] = array[i];
            }
        }
        std::array<int, 5> greater{};
        for (int i = 1; i < array.size(); ++i) {
            if (array[i] > pivot) {
                greater[i - 1] = array[i];
            }
        }
        // TODO 注意: 内置数组和std::array提供的功能有限, 没有提供两个数组相加的 + 运算符重载函数。
        //  所以想换成std::vector试一下。
        return quickSort(less) + [pivot]+quickSort(greater);*/

//        std::array<int, 5> less{};
            std::vector<int> less{};
            for (int i = 1; i < array.size(); ++i) {
                if (array[i] <= pivot) {
//                less[i - 1] = array[i];
                    less.push_back(array[i]);
                }
            }
//        std::array<int, 5> greater{};
            std::vector<int> greater{};
            for (int i = 1; i < array.size(); ++i) {
                if (array[i] > pivot) {
//                greater[i - 1] = array[i];
                    greater.push_back(array[i]);
                }
            }

            // 下面这几行的代码包括return语句在 Python 下为
            // return quicksort(less) + [pivot] + quicksort(greater)
            // 但是转化成C++就需要如下代码。

            // TODO 注意: 内置数组和std::array提供的功能有限, 没有提供两个数组相加的 + 运算符重载函数。
            //  所以想换成std::vector试一下。
            std::vector<int> vector = quickSort(less);
            // 下面这两句代码是等效的。
            vector.insert(vector.cend(), pivot);
//        vector.insert(vector.cend(), array[0]);
            const std::vector<int>& greaterTmp = quickSort(greater);
            // TODO 注意: std::array没有将一个std::array追加到另一个std::array结尾的算法,
            //  而std::vector提供了。
            vector.insert(vector.cend(), greaterTmp.cbegin(), greaterTmp.cend());
            return vector;
        }
    }

}
#endif
